package Algorithm.dynamicProgramming.introduct;

/**
 * 题目描述：有一堆数量为n的石子，小红和小紫轮流拿，每次拿的数量需属于正整数集合S，问最终小红能否获胜
 * 参考：https://www.cnblogs.com/tian-zai/p/16543249.html
 */
public class NimGame {

    /**
     * 若在dp[i - S[j]]小红必败，则在dp[i]最后一轮时，小红可以拿S[j]个，这样就把必败的困境留给了对方
     * 若在dp[i - S[j]]小红必胜，则在dp[i]最后一轮时，小紫可以拿S[j]个，把必胜的机会留给自己
     * 故dp[i] = !dp[i - S[j]]
     */
    public static boolean canWin(int n, int[] S) {
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;dp[1] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < S.length && S[j] <= i;j++) {
                if (!dp[i - S[j]]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5; // 你可以将 n 替换为实际的石子数量
        boolean result = canWin(n, new int[]{1,4});

        if (result) {
            System.out.println("小红可以获胜！");
        } else {
            System.out.println("小红无法获胜。");
        }
    }
}
